/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

package pratica7;

import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.HashMap;
import static pratica7.Peso.extractWeight;
import static pratica7.Peso.infinity;
import static pratica7.Peso.zero;

/**
 *
 * @author diego
 */
public class Dijkstra {
    
    public static HashMap<Vertice, ArrayList<Vertice>> dijkstra (JGrafo G, HashMap<AbstractMap.SimpleEntry<Vertice, Vertice>, Peso> weights, Vertice s) {
        HashMap<Vertice, ArrayList<Vertice>> S = new HashMap<>();
        HashMap<Vertice, Vertice> P = new HashMap <>();
        for (Vertice v : G.vertices) {
            v.key = infinity;
            P.put(v, null);
        }
        s.key = zero;
        MinHeap<Vertice> Q = new MinHeap<>(G.vertices);
        while (Q.size() != 0) {
            Vertice u = Q.pop();
            for (Vertice r : G.adjacencies(u)) {
                if (Peso.compare(r.key, Peso.sum(u.key , extractWeight(u, r, weights))) == 1) {
                    r.key = Peso.sum(u.key , extractWeight(u, r, weights));
                    P.put(r, u);
                }
            }
            Vertice t = u;
            ArrayList<Vertice> path = new ArrayList<>();
            path.add(t);
            while (P.get(t) != null) {
                path.add(P.get(t));
                t = P.get(t);
            }
            S.put(u, path);
        }
        return S;
    }
}
